/**
 * 给你两个整数数组arr1，arr2和一个整数d，请你返回两个数组之间的距离值。
 *
 * 「距离值」定义为符合此距离要求的元素数目：对于元素arr1[i]，不存在任何元素arr2[j]满足 |arr1[i]-arr2[j]| <= d 。
 *https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/
 *
 *先对arr2进行排序，之后遍历arr1，假设这个数为xx，因为d >= 0d>=0，如果arr2中存在一个数yy且满足num - d <= y <= num + dnum−d<=y<=num+d，那么arr1中的数xx就不满足题目要求。
 *
 * 重点是二分搜索。
 *
 
 */
class FindTheDistanceValue {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int num1 : arr1) {
            int low = num1 - d;
            int high = num1 + d;
            if (!binarySearch(arr2, low, high)) {
                ans++;
            }
        }

        return ans;
    }

    public static boolean binarySearch(int[] arr, int low, int high) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= low && arr[mid] <= high) {
                return true;
            } else if (arr[mid] < low) {
                left = mid + 1;
            } else if (arr[mid] > high) {
                right = mid - 1;
            }
        }

        return false;
    }
}

